package Sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/*
找出中间数，先把小于中间数的所有数放到左边，把大于中间数的所有数放在右边，然后左右递归
 */
public class QuickSort {

  public static void main(String[] args) {

//    int[] num = {-9,78,0,23,-567,70};
//    quickSort(num,0,num.length-1);
//    System.out.println("排序后的结果：" + Arrays.toString(num));

//    测试快速排序
    int num[] = new int[8000000];
    for (int i = 0; i < 8000000; i++) {
      num[i] = (int)(Math.random()*80000);//生成一个0到80000的数
    }
//    测试插入排序的效率
    Date date = new Date();
    SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy--MM-dd HH:mm:ss");
    String dateStr1 = simpleDateFormat.format(date);
    System.out.println("排序前的时间：" + dateStr1);

//    排序后
    quickSort(num,0,num.length-1);

    Date date2 = new Date();
    String dateStr2 = simpleDateFormat.format(date2);
    System.out.println("排序后的时间：" + dateStr2);

  }

  public static void quickSort(int[] arr,int left,int right){
    int l = left;
    int r = right;
    int temp = 0;

//    中轴值
    int pivot = arr[(left + right)/2];
    // while循环的目的是让比pivot值小放到左边
    // 比pivot值大放到右边
    while (l < r){
//      在pivot的左边一直找,找到大于等于pivot值,才退出
      while (arr[l] < pivot){
        l = l + 1;
      }
//      在pivot的右边一直找,找到小于等于pivot值,才退出
      while (arr[r] > pivot){
        r = r - 1;
      }
//      如果l>=r说明pivot的左右两的值，已经按照左边全部是小于等于pivot值,右边全部是大于等于pivot值
      if ( l >= r){
        break;
      }

//      交换
      temp = arr[l];
      arr[l] = arr[r];
      arr[r] = temp;
//      如果交换完后，发现这个arr[l] == pivot值相等--，前移
//     例如这种数组，则会出现下列情况 -1，10，-2，0，1，2,3
      if (arr[l] == pivot){
        r = r - 1;
      }
//      如果交换完后，发现这个arr[r] == pivot值相等++，后移
      if (arr[r] == pivot){
        l = l + 1;
      }
    }

//      如果1 == r，必须l++,r--,否则为出观栈溢出
    if (l == r){
      l++;
      r--;
    }
//      向左递归
    if (left < r){
      quickSort(arr,left,r);
    }
//      向右递归
    if (right > l){
      quickSort(arr,l,right);
    }

  }
}
